package day11;

/**
 * @author aiPlusPlus
 * @version 1.0
 * @date 2023/4/11 18:37
 */

/**
 * 力扣嘉年华的花店中从左至右摆放了一排鲜花，记录于整型一维矩阵 中每个数字表示该位置所种鲜花的品种编号。你可以选择一段区间的鲜花做成插花，且不能丢弃。 在你选择的插花中，如果每一品种的鲜花数量都不超过 朵，那么我们认为这束插花是 「美观的」。flowerscnt
 * <p>
 * 例如： 中品种为 的花有 朵， 品种为 的花有 朵，每一品种 的数量均不超过 [5,5,5,6,6]53623
 * 请返回在这一排鲜花中，共有多少种可选择的区间，使得插花是「美观的」。
 * <p>
 * 注意：
 * <p>
 * 答案需要以 为底取模，如：计算初始结果为：，请返回 1e9 + 7 (1000000007)10000000081
 * 示例 1：
 * <p>
 * 输入：flowers = [1,2,3,2], cnt = 1
 * <p>
 * 输出：8
 * <p>
 * 解释：相同的鲜花不超过 朵，共有 种花束是美观的； 长度为 的区间 均满足条件，共 种可选择区间 长度为 的区间 均满足条件，共 种可选择区间 长度为 的区间 满足条件，共 种可选择区间。 区间 都包含了 朵鲜花 ，不满足条件。 返回总数 181[1]、[2]、[3]、[2]42[1,2]、[2,3]、[3,2]33[1,2,3]1[2,3,2],[1,2,3,2]224+3+1 = 8
 * <p>
 * 示例 2：
 * <p>
 * 输入：flowers = [5,3,3,3], cnt = 2
 * <p>
 * 输出：8
 */
public class Solution2 {
    public int beautifulBouquet(int[] flowers, int cnt) {
        long mod=1000000007;
        int left=0;
        int n=flowers.length;
        long res=0;
        int[] count=new int[100001];
        for(int i=0;i<n;i++){
            count[flowers[i]]++;
            while(count[flowers[i]]>cnt){
                count[flowers[left]]--;
                left++;
            }
            res += i - left + 1;
        }
        return (int) (res % mod);
    }
}
